package com.cjm.algorithm.leetcode;

import com.cjm.algorithm.TreeNode;

/**
 * 235gn 236不同的是, 236不是二叉搜索树
 */
public class LowestCommonAncestor235 {

    public static TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {

        if(root == null || p.val == root.val || q.val == root.val) {
            return root;
        }
        TreeNode left = lowestCommonAncestor1(root.left, p, q);
        TreeNode right = lowestCommonAncestor1(root.right, p, q);
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        return root;
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 这道题与236的不同是什么呢?
        while ((root.val  - p.val) * (root.val * q.val) > 0) {
            // 如果能进来, 证明p与q在root的同一侧
            // 那么此时就要更新root
            root = root.val - p.val > 0 ? root.left:root.right;
        }

        return root;
    }

    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.generatorTreeNode(new Integer[]{6, 2, 8, 0, 4, 7, 9, null, null, 3, 5});
        TreeNode treeNode1 = lowestCommonAncestor(treeNode, new TreeNode(2), new TreeNode(4));
        System.err.println("OK");
    }
}
